//
// Created by 下次一定 on 2021/9/21.
//

/*
 *对优化版的dijkstra算法
 * */


#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int,int>PII;
const int N = 10;
int h[N], w[N] , e[N], ne[N];
int dist[N];
int n, m, idx;
bool st[N];


int dijkstra() {
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;

    //实现小根堆
    priority_queue<PII,vector<PII>,greater<PII>>heap;
    heap.push({0,1});

    while(heap.size()){
        auto t = heap.top();
        heap.top();
        int ver = t.second,distance = t.first;
        if(st[ver]) continue;
        for(int i = h[ver]; i!=-1 ; i = ne[i]){
            int j = e[i];
            if(dist[j] > distance + w[i]){
                dist[j] = distance + w[i];
                heap.push({dist[j],j});
            }
        }
    }

    if (dist[n] == 0x3f) return -1;
    return dist[n];
}

void add(int a,int b ,int c){
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
    idx++;
}
int main() {
    cin >> n >> m;

   memset(h,-1,sizeof h );

    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a;
        cin >> b;
        cin >> w;
        add(a,b,w);
    }

    int t = dijkstra();

    cout << t << endl;
}

